package one.collectionAndMap;

import java.util.HashSet;
import java.util.Set;

/**
 * 模拟行走机器人
 * 时间复杂度：O(nm)
 * 思路：1）写Hash函数；2）方向数组，障碍物
 * 1）写Hash函数；
 * 第一种思路：（-200,30000）==》String："-200,30000"==>集合set里有有关String的Hash函数（但是没有有关二元组或者数组的Hash函数）
 * 第二种思路：数值之间的进制转化
 *      long:(-200,30000)==>(-200+30000, 30000+30000)==>(-200+30000)*60000+(30000+30000)
 *      60000的进制转化
 */
public class RobotSim {

    public static int robotSim(int[] commands, int[][] obstacles) {
        Set<String> blockers = new HashSet<>();
        for(int[] obstacle : obstacles){
            blockers.add(calcHash(obstacle[0], obstacle[1])); //hash
        }

        //方向数组技巧
        //                  N   E  S  W
        int[] dx = new int[]{0, 1, 0, -1}; //偏移量
        int[] dy = new int[]{1, 0, -1, 0};
        int x = 0, y = 0; //起始坐标（原点0,0）
        int dir = 0; //起始方向 N
        int ans = 0; //答案
        for(int cmd : commands){
            if(cmd > 0){ //是命令
                for (int i = 0; i < cmd; i++){
                    //尝试走到(nextx,nexty)
                    int nextx = x + dx[dir];
                    int nexty = y + dy[dir];
                    //有障碍物
                    if(blockers.contains(calcHash(nextx, nexty))){
                        break;
                    }
                    //走一步
                    x = nextx;
                    y = nexty;
                    ans = Math.max(ans, x * x + y * y);
                }
            }else if(cmd == -1){ //右转（顺时针）
                //0-->1-->2-->3-->0
                //N-->E-->S-->W-->N
                dir = (dir + 1) % 4;
            }else { //左转
                dir = (dir - 1 + 4) % 4; //避免出现负数，所以加上一个模数mod”4“
            }
        }
        return ans;
    }
    private static String calcHash(int x, int y){//自定义Hash函数（第一种思路：String）
        return x + "," + y;
    }
//    private long calcHash(int x, int y){//自定义Hash函数（第二种思路：数值间的进制转换）
//        return (x + 30000) * 60000L + (y + 30000);
//    }

    public static void main(String[] args) {
        //输入：commands = [4,-1,4,-2,4], obstacles = [[2,4]]
        //输出：65
        int[] commands = {4, -1, 4, -2, 4};
        int[][] obstacles = {{2, 4}};
        int answer = robotSim(commands, obstacles);
        System.out.println(answer);
    }
}
